package 中等.哈希表;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个仅由小写英文字母组成的字符串 s 。
 * 如果一个字符串仅由单一字符组成，那么它被称为 特殊 字符串。例如，
 * 字符串 "abc" 不是特殊字符串，而字符串 "ddd"、"zz" 和 "f" 是特殊字符串。
 * 返回在 s 中出现 至少三次 的 最长特殊子字符串 的长度，
 * 如果不存在出现至少三次的特殊子字符串，则返回 -1 。
 * 子字符串 是字符串中的一个连续 非空 字符序列。
 *
 * @ https://leetcode.cn/problems/find-longest-special-substring-that-occurs-thrice-i/description/
 * @date 2024/01/01
 */
public class 找出出现至少三次的最长特殊子字符串I {

    public static void main(String[] args) {

    }

    /**
     * 双层循环+哈希表
     */
    public static int maximumLength(String s) {
        int maxLen = -1;
        // 某个字符，特殊字符串长度为 len 的出现几次
        Map<Character, Map<Integer, Integer>> mapMap = new HashMap<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            Map<Integer, Integer> cntMap = mapMap.get(chars[i]);
            if (cntMap == null) {
                cntMap = new HashMap<>();
                mapMap.put(chars[i], cntMap);
            }
            for (int j = i; j >= 0 && chars[j] == chars[i]; j--) {
                int curLen = i - j + 1;
                cntMap.put(curLen, cntMap.getOrDefault(curLen, 0) + 1);
                if (cntMap.get(curLen) >= 3) {
                    maxLen = Math.max(maxLen, curLen);
                }
            }
        }

        return maxLen;
    }

}
